#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <math.h>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
#include <sstream>
using namespace std;
const int N = 20;
int n;
bool map_use[N][N];
int key[N];
int cnt = 0;
void diagonal_use(int row, int col)
{
	if (row>n||col<1||col>n)return;
	int j = 1;
	for (int i = row; i <= n; i++,j++)
	{
		map_use[i][col] = true;
		if(col+j<=n && i + 1 <= n)
			map_use[i+1][col+j] = true;
		if(col-j>=1 && i + 1 <= n)
			map_use[i+1][col-j] = true;
	}
}
void dfs(int row)
{
	if (row > n)
	{
		cnt++;
		if(cnt<=3)
		{
			for (int i = 1; i <= n; i++)
			{
				printf("%d ", key[i]);
			}
			printf("\n");
		}
		return;
	}
	for (int col = 1; col <= n; col++)
	{
		if (map_use[row][col]==false)
		{
			bool tmp_restore[N][N] = { false };
			memcpy(tmp_restore, map_use, sizeof(map_use));
			diagonal_use(row, col);
			key[row] = col;
			dfs(row + 1);
			memcpy(map_use, tmp_restore, sizeof(map_use));
		}
	}
}
int main()
{
	cin >> n;
	dfs(1);
	cout << cnt;
	return 0;
}